//图类 二维数组，其中的元素表示两个顶点之间是否有一条边。
function Graph(v) {
    this.vertices = v;
    this.edges = 0;
    this.adj = [];
    for (var i = 0; i < this.vertices; i++) {
        this.adj[i] = [];
    }
    this.marked = [];
    for (var i = 0; i < this.vertices; i++) {
        this.marked[i] = false;
    }
    this.edgeTo = [];//在bfs 保存从一个顶点到下一个顶点的所有边
}

Graph.prototype = {
    addEdge: function (v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    },
    //深度优先
    //访问一个没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。
    dfs: function (v) {
        this.marked[v] = true;
        console.log(v);
        for (var i = 0; i < this.adj[v].length; i++) {
            if (!this.marked[this.adj[v][i]]) {
                this.dfs(this.adj[v][i])
            }
        }
    },
    //广度优先搜索算法使用了抽象的队列而不是数组来对已访问过的顶点进行排序。其算法的工作原理如下：
    //(1) 查找与当前顶点相邻的未访问顶点，将其添加到已访问顶点列表及队列中；
    //(2) 从图中取出下一个顶点v，添加到已访问的顶点列表；
    //(3) 将所有与v 相邻的未访问顶点添加到队列
    bfs: function (v) {
        var queue = [];
        this.marked[v] = true;
        queue.push(v);
        while (queue.length > 0) {
            var s = queue.shift();
            console.log(s);
            for (var i = 0; i < this.adj[s].length; i++) {
                if (!this.marked[this.adj[s][i]]) {
                    this.edgeTo[this.adj[s][i]] = v;
                    this.marked[this.adj[s][i]] = true;
                    queue.push(this.adj[s][i]);
                }
            }
        }
    },
    //寻找最短路径
    //创建了一个栈，用来存储与指定顶点有共同边的所有顶点
    pathTo: function (v) {
        var source = 0;
        if (!this.hasPathTo(v)) {
            return undefined;
        }
        var path = [];
        for (var i = v; i != source; i = this.edgeTo[i]) {
            path.push(i);
        }
        //path.push(s);
        return path;
    },
    hasPathTo(v) {
        return this.marked[v]
    }
};